Коммивояжёра задача - определение. Что такое Коммивояжёра задача
Diclib.com
Словарь ChatGPT
Введите слово или словосочетание на любом языке 👆
Язык:

Перевод и анализ слов искусственным интеллектом ChatGPT

На этой странице Вы можете получить подробный анализ слова или словосочетания, произведенный с помощью лучшей на сегодняшний день технологии искусственного интеллекта:

  • как употребляется слово
  • частота употребления
  • используется оно чаще в устной или письменной речи
  • варианты перевода слова
  • примеры употребления (несколько фраз с переводом)
  • этимология

Что (кто) такое Коммивояжёра задача - определение

ОДНА ИЗ САМЫХ ИЗВЕСТНЫХ ЗАДАЧ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ, ЗАКЛЮЧАЮЩАЯСЯ В ПОИСКЕ САМОГО ВЫГОДНОГО МАРШРУТА
Задача коммивояжера; Задача о коммивояжере; Задача о коммивояжёре; Коммивояжёра задача; Метод эластичной сети; Эластичная сеть
  • 43589145600}} вариантов.
  • Гамильтон Уильям Роуэн

Коммивояжёра задача         

задача о бродячем торговце, одна из известных задач конечной математики (См. Конечная математика); в простейшем случае формулируется следующим образом: даны n городов и известны расстояния между каждыми двумя городами; коммивояжёр, выходящий из какого-нибудь города, должен посетить n - 1 других городов и вернуться в исходный. В каком порядке ему нужно посещать города (по одному разу каждый), чтобы общее пройденное расстояние было минимальным. К такого типа задачам, связанным с объездом ряда пунктов и возвращением в исходную точку, относятся: задачи доставки продуктов питания в магазины, подвода электроэнергии к потребителям, построения кольцевой линии электропередач, различные задачи, возникающие при автоматизации монтажа схем, и т.д. Такова, например, задача отыскания оптимальной программы работы автоматического фрезерного станка для просверливания отверстий в заданных точках панели радиоприёмника, то есть нахождения такого порядка прохождения этих точек, при котором длина маршрута головки сверла была бы минимальной. Здесь начало маршрута не обязательно должно совпадать с его концом, но математически такая постановка сводится к приведенной выше простейшей К. з. Методы решения К. з., по существу, сводятся к организации полного перебора вариантов; никакого эффективного алгоритма не известно.

Лит.: Мудров В. И., Задача о коммивояжёре, М., 1969; Гольштеин Е. Г., Юдин Д. Б., Новые направления в линейном программировании, М., 1966.

В. П. Козырев.

Задача коммивояжёра         
Задача коммивояжёра (или TSP от ) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного.
Задача Аполлония         
ЗАДАЧА НА ПОСТРОЕНИЕ
Задача Аполония
Зада́ча Аполло́ния — построить с помощью циркуля и линейки окружность, касающуюся трёх данных окружностей.

Википедия

Задача коммивояжёра

Задача коммивояжёра (или TSP от англ. travelling salesman problem) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. Существует несколько частных случаев общей постановки задачи, в частности, геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), метрическая задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.

Оптимизационная постановка задачи относится к классу NP-трудных задач, впрочем, как и большинство её частных случаев. Версия «decision problem» (то есть такая, в которой ставится вопрос, существует ли маршрут не длиннее, чем заданное значение k) относится к классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (>66) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.

Что такое Коммивояжёра зад<font color="red">а</font>ча - определение